# 先序遍历
def hasPathSum(self, root, sum):
    # write code here
    if not root: return
    return self.preOrder(root, sum, 0)


def preOrder(self, root, sum, cur):
    if not root: return
    cur += root.val
    if not root.left and not root.right and cur == sum:
        return True
    return self.preOrder(root.left, sum, cur) or self.preOrder(root.right, sum, cur)

# 精简递归
class Solution:
    def hasPathSum(self , root , sum ):
        # write code here
        if not root: return
        sum -= root.val
        if sum == 0 and not root.left and not root.right:
            return True
        return self.hasPathSum(root.left,sum) or self.hasPathSum(root.right,sum)
#or是语法糖 如果root.left和root.right都存在，同时返回。否则返回之一。